// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package runtime

// 此文件包含Go映射类型的实现。
// 
// 映射只是一个哈希表。数据按
// 排列成一个存储桶数组。每个存储桶最多包含
// 8个密钥/元素对。散列的低位是
// 用于选择一个bucket。每个bucket包含每个hash的几个
// 高阶位，以区分单个bucket中的条目
// 。
// 
// 如果一个存储桶中散列了8个以上的键，我们将在
// 额外存储桶上进行链接。
// 
// 当哈希表增长时，我们分配一个新数组
// 的桶是原来的两倍大。bucket是递增的
// 从旧bucket数组复制到新bucket数组。
// 
// 映射迭代器遍历bucket数组，
// 按遍历顺序返回键（bucket#，然后溢出
// 链顺序，然后返回bucket索引）。为了维护迭代
// 语义，我们从不在它们的bucket中移动键（如果
// 我们移动了，键可能会返回0或2次）。当
// 增加表时，迭代器仍在对
// 旧表进行迭代，并且必须检查新表是否已将其迭代的桶
// 移动（“排空”）
// 到新表。

// 拣选装载系数：太大，我们有很多溢出
// 桶太小，我们浪费了很多空间。我写了一个简单的程序来检查不同负载的一些统计信息：64位，8字节的键和元素
// loadFactor%溢出字节/条目hitprobe missprobe 
// 4.00 2.13 20.77 3.00 4.00 
// 4.50 4.05 17.30 3.25 4.50 
// 5.00 6.85 14.77 3.50 5.00 
// /5.50 10.55 12.94 3.75 5.50 
// 8.00 41.10 9.40 5.00 8.00 
// 
// %overflow=具有溢出存储桶的存储桶百分比
// /字节/条目=每个密钥/元素对使用的开销字节
// missprobe=#查找缺少键
// 
// 请记住，此数据用于最大负载的表，即在表增长之前，仅
// 要检查的项。典型的表将稍微少一些加载。

import (
	"runtime/internal/atomic"
	"runtime/internal/math"
	"runtime/internal/sys"
	"unsafe"
)

const (
	// 一个存储桶可以容纳的最大密钥/元素对数。
	bucketCntBits = 3
	bucketCnt     = 1 << bucketCntBits

	// 触发增长的铲斗最大平均负载为6.5。
	// 表示为loadFactorNum/loadFactorDen，以允许整数数学。
	loadFactorNum = 13
	loadFactorDen = 2

	// 保持内联的最大键或元素大小（而不是每个元素的mallocing）。
	// 必须安装在单元8中。
	// 快速版本无法处理大元素-cmd/compile/internal/gc/walk.go中的
	// 快速版本的截止大小必须最多为该元素。
	maxKeySize  = 128
	maxElemSize = 128

	// 数据偏移量应为bmap结构的大小，但需要正确对齐。对于amd64p32，这意味着64位对齐
	// 即使指针是32位的。
	dataOffset = unsafe.Offsetof(struct {
		b bmap
		v int64
	}{}.v)

	// 可能的tophash值。我们保留一些特殊标记的可能性。
	// 每个存储桶（包括其溢出存储桶，如果有的话）的所有或任何
	// 条目都将处于疏散*状态（在EXCUVATE（）方法期间除外，该方法仅在映射写入期间发生，因此在此期间其他人无法观察映射）。
	emptyRest      = 0 // 此单元格为空，并且在较高索引或溢出处不再有非空单元格。
	emptyOne       = 1 // 此单元格为空
	evacuatedX     = 2 // key/elem有效。入口已经疏散到大桌子的前半部分。
	evacuatedY     = 3 // 同上，但疏散到大桌子的下半部分。
	evacuatedEmpty = 4 // 电池为空，桶已排空。
	minTopHash     = 5 // 正常填充单元格的最小tophash。

	// 标志
	iterator     = 1 // 可能有一个迭代器使用bucket 
	oldIterator  = 2 // 可能有一个迭代器使用旧bucket 
	hashWriting  = 4 // 一个goroutine正在写入映射
	sameSizeGrow = 8 // 当前映射增长到一个相同大小的新映射

	// 用于迭代器检查的sentinel bucket ID 
	noCheck = 1<<(8*sys.PtrSize) - 1
)

// I空报告给定的tophash数组项是否表示空的bucket项。
func isEmpty(x uint8) bool {
	return x <= emptyOne
}

// 围棋地图的标题。
type hmap struct {
	// 注意：hmap的格式也用cmd/compile/internal/reflectdata/reflect.go编码。
	// 确保它与编译器的定义保持同步。
	count     int // /#活细胞==地图大小。必须是第一个（由len（）内置使用）
	flags     uint8
	B         uint8  // log#2个存储桶（最多可容纳loadFactor*2^B项）
	noverflow uint16 // 溢出存储桶的大致数量；有关详细信息，请参见incrnoverflow 
	hash0     uint32 // 哈希种子

	buckets    unsafe.Pointer // 2^B桶的数组。如果计数=0，则可能为零。
	oldbuckets unsafe.Pointer // 上一个大小为一半的桶数组，仅在增长时为非零
	nevacuate  uintptr        // 用于疏散的进度计数器（小于此值的桶已被疏散）

	extra *mapextra // 可选字段
}

// mapextra保留所有地图上不存在的字段。
type mapextra struct {
	// 如果key和elem都不包含指针并且都是内联的，那么我们将bucket 
	// 类型标记为不包含指针。这样可以避免扫描此类地图。
	// 但是，bmap.overflow是一个指针。为了使溢出桶
	// 保持活动状态，我们在hmap.extra.overflow和hmap.extra.oldoverflow中存储指向所有溢出桶的指针。
	// 仅当key和elem不包含指针时才使用溢出和oldoverflow。
	// 溢出包含hmap.bucket的溢出桶。
	// oldoverflow包含hmap.oldBucket的溢出桶。
	// 间接寻址允许在hiter中存储指向切片的指针。
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// nextOverflow持有指向空闲溢出桶的指针。
	nextOverflow *bmap
}

// 一个桶装一张围棋地图。
type bmap struct {
	// tophash通常包含此bucket中每个键的哈希值
	// 的顶部字节。如果tophash[0]<minTopHash，则
	// tophash[0]为桶排空状态。
	tophash [bucketCnt]uint8
	// 后跟bucketCnt键，然后是bucketCnt元素。
	// 注意：将所有键打包在一起，然后将所有元素打包在一起，这使得
	// 代码比交替键/elem/key/elem/复杂一些。。。但它允许
	// /我们消除可能需要的填充，例如map[int64]int8。
	// 后跟一个溢出指针。
}

// 一种哈希迭代结构。
// 如果修改hiter，也可以更改cmd/compile/internal/reflectdata/reflect.go以指示
// 此结构的布局。
type hiter struct {
	key         unsafe.Pointer // 必须在第一个位置。写nil表示迭代结束（参见cmd/compile/internal/walk/range.go）。
	elem        unsafe.Pointer // 必须位于第二个位置（请参阅cmd/compile/internal/walk/range.go）。
	t           *maptype
	h           *hmap
	buckets     unsafe.Pointer // 哈希表初始化时的bucket ptr 
	bptr        *bmap          // 当前bucket 
	overflow    *[]*bmap       // 保持hmap.bucket的溢出bucket活动
	oldoverflow *[]*bmap       // 保持hmap.oldBucket的溢出bucket活动
	startBucket uintptr        // 在
	wrapped     bool           // 已经从bucket数组的末尾到开始
	B           uint8
	i           uint8
	bucket      uintptr
	checkBucket uintptr
}

// bucketShift返回1<<b，为代码生成而优化。
func bucketShift(b uint8) uintptr {
	// 掩蔽移位量允许省略溢出检查。
	return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}

// bucketMask返回1<<b-1，为生成代码而优化。
func bucketMask(b uint8) uintptr {
	return bucketShift(b) - 1
}

// tophash计算哈希的tophash值。
func tophash(hash uintptr) uint8 {
	top := uint8(hash >> (sys.PtrSize*8 - 8))
	if top < minTopHash {
		top += minTopHash
	}
	return top
}

func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > emptyOne && h < minTopHash
}

func (b *bmap) overflow(t *maptype) *bmap {
	return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
}

func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
	*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
}

func (b *bmap) keys() unsafe.Pointer {
	return add(unsafe.Pointer(b), dataOffset)
}

// incrnoverflow增加h.noverflow。
// noverflow统计溢出桶的数量。
// 用于触发相同大小的贴图增长。
// 另请参见太多溢流桶。
// 为了保持hmap较小，noverflow是一个uint16。
// 当存储桶很少时，noverflow是一个精确的计数。
// 当存在多个存储桶时，noverflow是一个近似计数。
func (h *hmap) incrnoverflow() {
	// 如果有
	// 溢出存储桶的数量与存储桶的数量相同，我们将触发相同大小的映射增长。
	// 我们需要能够计数到1<<h.B.
	if h.B < 16 {
		h.noverflow++
		return
	}
	// 以概率1/（1<<h.B-15）递增。
	// 当我们达到1<<15-1时，我们将有大约
	// 与桶一样多的溢出桶。
	mask := uint32(1)<<(h.B-15) - 1
	// 示例：如果h.B==18，那么mask==7，
	// 和fastrand&7==0，概率为1/8。
	if fastrand()&mask == 0 {
		h.noverflow++
	}
}

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
	var ovf *bmap
	if h.extra != nil && h.extra.nextOverflow != nil {
		// 我们有预分配的溢出桶可用。
		// 有关更多详细信息，请参阅makeBucketArray。
		ovf = h.extra.nextOverflow
		if ovf.overflow(t) == nil {
			// 我们还没有到预分配溢出桶的末尾。碰一下指针。
			h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
		} else {
			// 这是最后一个预分配的溢出桶。
			// 重置此存储桶上的溢出指针，
			// 该值设置为非nil sentinel值。
			ovf.setoverflow(t, nil)
			h.extra.nextOverflow = nil
		}
	} else {
		ovf = (*bmap)(newobject(t.bucket))
	}
	h.incrnoverflow()
	if t.bucket.ptrdata == 0 {
		h.createOverflow()
		*h.extra.overflow = append(*h.extra.overflow, ovf)
	}
	b.setoverflow(t, ovf)
	return ovf
}

func (h *hmap) createOverflow() {
	if h.extra == nil {
		h.extra = new(mapextra)
	}
	if h.extra.overflow == nil {
		h.extra.overflow = new([]*bmap)
	}
}

func makemap64(t *maptype, hint int64, h *hmap) *hmap {
	if int64(int(hint)) != hint {
		hint = 0
	}
	return makemap(t, int(hint), h)
}

// makemap_小实现为make（map[k]v）和
// make（map[k]v，hint）创建映射，在编译时已知hint最多为bucketCnt 
// 并且需要在堆上分配映射。
func makemap_small() *hmap {
	h := new(hmap)
	h.hash0 = fastrand()
	return h
}

// makemap实现make的Go映射创建（map[k]v，hint）。
// 如果编译器已确定可以在堆栈上创建映射或第一个bucket 
// 则h和/或bucket可能为非零。
// 如果h！=nil，则可以直接在h中创建映射。
// 如果是h.Bucket！=无，指向的桶可以用作第一个桶。
func makemap(t *maptype, hint int, h *hmap) *hmap {
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	// 初始化Hmap 
	if h == nil {
		h = new(hmap)
	}
	h.hash0 = fastrand()

	// 查找将保存所请求元素的大小参数B。
	// For hint<0重载因子返回false，因为hint<bucketCnt。
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// 分配初始哈希表
	// 如果B==0，则稍后（在mapassign中）延迟分配Bucket字段
	// 如果提示较大，则将此内存归零可能需要一段时间。
	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

// makebucketaray初始化映射桶的备份数组。
// 1<<b是要分配的最小桶数。
// dirtyalloc应该是nil，或者是以前由makeBucketArray使用相同的t和b参数分配的bucket数组
// 。
// 如果dirtyalloc为nil，则将分配新的支持数组，否则将清除dirtyalloc并将其重新用作支持数组。
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b)
	nbuckets := base
	// 对于小型b，溢出桶不太可能出现。
	// 避免计算的开销。
	if b >= 4 {
		// 加上溢出桶的估计数量
		// 插入元素的中值
		// 需要与此值b一起使用。
		nbuckets += bucketShift(b - 4)
		sz := t.bucket.size * nbuckets
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.bucket.size
		}
	}

	if dirtyalloc == nil {
		buckets = newarray(t.bucket, int(nbuckets))
	} else {
		// dirtyalloc以前是由
		// 上述新数组（t.bucket，int（nbuckets））生成的，但不能为空。
		buckets = dirtyalloc
		size := t.bucket.size * nbuckets
		if t.bucket.ptrdata != 0 {
			memclrHasPointers(buckets, size)
		} else {
			memclrNoHeapPointers(buckets, size)
		}
	}

	if base != nbuckets {
		// 我们预先分配了一些溢出桶。
		// 为了将跟踪这些溢出桶的开销保持在最低限度，我们使用一种约定，即如果预分配的溢出桶的溢出
		// 指针为零，则通过碰撞指针可以获得更多可用性。
		// 最后一个溢出桶需要一个安全的非零指针；就用水桶吧。
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}

// mapaccess1返回指向h[key]的指针。从不返回nil，而是
// 如果键不在映射中，它将返回对元素类型的零对象的引用。
// 注意：返回的指针可能会使整个映射保持活动状态，因此不要长时间保留它。
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapaccess1)
		racereadpc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		msanread(key, t.key.size)
	}
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // 见23734期
		}
		return unsafe.Pointer(&zeroVal[0])
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	hash := t.hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	if c := h.oldbuckets; c != nil {
		if !h.sameSizeGrow() {
			// 过去桶的数量是现在的一半；掩盖二的一次幂。
			m >>= 1
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
	top := tophash(hash)
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if t.key.equal(key, k) {
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
				return e
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapaccess2)
		racereadpc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		msanread(key, t.key.size)
	}
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // 参见23734期
		}
		return unsafe.Pointer(&zeroVal[0]), false
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	hash := t.hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	if c := h.oldbuckets; c != nil {
		if !h.sameSizeGrow() {
			// 过去桶的数量是现在的一半；掩盖二的一次幂。
			m >>= 1
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
	top := tophash(hash)
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if t.key.equal(key, k) {
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
				return e, true
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0]), false
}

// 返回键和元素。由映射迭代器
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
	if h == nil || h.count == 0 {
		return nil, nil
	}
	hash := t.hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	if c := h.oldbuckets; c != nil {
		if !h.sameSizeGrow() {
			// /使用，以前有一半的桶；掩盖二的一次幂。
			m >>= 1
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
	top := tophash(hash)
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if t.key.equal(key, k) {
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
				return k, e
			}
		}
	}
	return nil, nil
}

func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer {
	e := mapaccess1(t, h, key)
	if e == unsafe.Pointer(&zeroVal[0]) {
		return zero
	}
	return e
}

func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {
	e := mapaccess1(t, h, key)
	if e == unsafe.Pointer(&zeroVal[0]) {
		return zero, false
	}
	return e, true
}

// 与mapaccess类似，但如果密钥不在映射中，则为其分配一个插槽。
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
	if raceenabled {
		callerpc := getcallerpc()
		pc := funcPC(mapassign)
		racewritepc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled {
		msanread(key, t.key.size)
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
	hash := t.hasher(key, uintptr(h.hash0))

	// 在调用t.hasher之后设置hashWriting，因为t.hasher可能会死机，
	// 在这种情况下，我们实际上没有进行写入。
	h.flags ^= hashWriting

	if h.buckets == nil {
		h.buckets = newobject(t.bucket) // 新数组（t.bucket，1）
	}

again:
	bucket := hash & bucketMask(h.B)
	if h.growing() {
		growWork(t, h, bucket)
	}
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
	top := tophash(hash)

	var inserti *uint8
	var insertk unsafe.Pointer
	var elem unsafe.Pointer
bucketloop:
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if isEmpty(b.tophash[i]) && inserti == nil {
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
					elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				}
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if !t.key.equal(key, k) {
				continue
			}
			// 已具有密钥的映射。更新它。
			if t.needkeyupdate() {
				typedmemmove(t.key, k, key)
			}
			elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
			goto done
		}
		ovf := b.overflow(t)
		if ovf == nil {
			break
		}
		b = ovf
	}

	// 未找到密钥的映射。分配新单元格并添加条目。ABCFDG 

	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again // 增加表会使所有内容无效，请重试
	}

	if inserti == nil {
		// 当前存储桶以及与之连接的所有溢出存储桶已满，请分配一个新的存储桶。
		newb := h.newoverflow(t, b)
		inserti = &newb.tophash[0]
		insertk = add(unsafe.Pointer(newb), dataOffset)
		elem = add(insertk, bucketCnt*uintptr(t.keysize))
	}

	// 在插入位置存储新密钥/元素
	if t.indirectkey() {
		kmem := newobject(t.key)
		*(*unsafe.Pointer)(insertk) = kmem
		insertk = kmem
	}
	if t.indirectelem() {
		vmem := newobject(t.elem)
		*(*unsafe.Pointer)(elem) = vmem
	}
	typedmemmove(t.key, insertk, key)
	*inserti = top
	h.count++

done:
	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting
	if t.indirectelem() {
		elem = *((*unsafe.Pointer)(elem))
	}
	return elem
}

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapdelete)
		racewritepc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		msanread(key, t.key.size)
	}
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // 请参阅问题23734 
		}
		return
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}

	hash := t.hasher(key, uintptr(h.hash0))

	// 在调用t.hasher后设置hashWriting，因为t.hasher可能会死机，
	// 在这种情况下，我们实际上没有执行写入（删除）。
	h.flags ^= hashWriting

	bucket := hash & bucketMask(h.B)
	if h.growing() {
		growWork(t, h, bucket)
	}
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
	bOrig := b
	top := tophash(hash)
search:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break search
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			k2 := k
			if t.indirectkey() {
				k2 = *((*unsafe.Pointer)(k2))
			}
			if !t.key.equal(key, k2) {
				continue
			}
			// 只有在有指针时才清除键。
			if t.indirectkey() {
				*(*unsafe.Pointer)(k) = nil
			} else if t.key.ptrdata != 0 {
				memclrHasPointers(k, t.key.size)
			}
			e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
			if t.indirectelem() {
				*(*unsafe.Pointer)(e) = nil
			} else if t.elem.ptrdata != 0 {
				memclrHasPointers(e, t.elem.size)
			} else {
				memclrNoHeapPointers(e, t.elem.size)
			}
			b.tophash[i] = emptyOne
			// 如果桶现在以一堆空状态结束，则
			// 将这些状态更改为最空状态。
			// 将其作为一个单独的函数会很好，但
			// for循环当前不可内联。
			if i == bucketCnt-1 {
				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
					goto notLast
				}
			} else {
				if b.tophash[i+1] != emptyRest {
					goto notLast
				}
			}
			for {
				b.tophash[i] = emptyRest
				if i == 0 {
					if b == bOrig {
						break // 初始桶的开始，我们完成了。
					}
					// 查找上一个存储桶，在其最后一个条目处继续。
					c := b
					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
					}
					i = bucketCnt - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}
		notLast:
			h.count--
			// 重置哈希种子，使攻击者更难重复触发哈希冲突。见第25237期。
			if h.count == 0 {
				h.hash0 = fastrand()
			}
			break search
		}
	}

	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting
}

// mapiterinit初始化用于在地图上测距的hiter结构。
// 由'it'指向的hiter结构在堆栈上分配
// 由编译器顺序传递或由reflect\u mapiterinit在堆上分配。
// 由于结构包含指针，所以两者都需要将命中率归零。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
	}

	if h == nil || h.count == 0 {
		return
	}

	if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {
		throw("hash_iter size incorrect") // 请参阅cmd/compile/internal/reflectdata/reflect.go 
	}
	it.t = t
	it.h = h

	// 抓取存储桶状态的快照
	it.B = h.B
	it.buckets = h.buckets
	if t.bucket.ptrdata == 0 {
		// 分配当前片并记住指向当前和旧片的指针。
		// 这将保留所有相关的溢出桶处于活动状态，即使
		// 在我们进行迭代时，表会增长和/或将溢出桶添加到表
		// 中。
		h.createOverflow()
		it.overflow = h.extra.overflow
		it.oldoverflow = h.extra.oldoverflow
	}

	// 决定从何处开始
	r := uintptr(fastrand())
	if h.B > 31-bucketCntBits {
		r += uintptr(fastrand()) << 31
	}
	it.startBucket = r & bucketMask(h.B)
	it.offset = uint8(r >> h.B & (bucketCnt - 1))

	// 迭代器状态
	it.bucket = it.startBucket

	// 记住我们有一个迭代器。
	// 可以与另一个mapiterinit（）同时运行。ABCFDG 
	if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
		atomic.Or8(&h.flags, iterator|oldIterator)
	}

	mapiternext(it)
}

func mapiternext(it *hiter) {
	h := it.h
	if raceenabled {
		callerpc := getcallerpc()
		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map iteration and map write")
	}
	t := it.t
	bucket := it.bucket
	b := it.bptr
	i := it.i
	checkBucket := it.checkBucket

next:
	if b == nil {
		if bucket == it.startBucket && it.wrapped {
			it.key = nil
			it.elem = nil
			return
		}
		if h.growing() && it.B == h.B {
			// 如果我们正在查看的桶尚未填充（即旧
			// 桶尚未排空），那么我们需要遍历旧
			// 桶，只返回将迁移到此桶的桶。AbDefg
			oldbucket := bucket & it.h.oldbucketmask()
			b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
			if !evacuated(b) {
				checkBucket = bucket
			} else {
				b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
				checkBucket = noCheck
			}
		} else {
			b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
			checkBucket = noCheck
		}
		bucket++
		if bucket == bucketShift(it.B) {
			bucket = 0
			it.wrapped = true
		}
		i = 0
	}
	for ; i < bucketCnt; i++ {
		offi := (i + it.offset) & (bucketCnt - 1)
		if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
			continue
		}
		k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
		if t.indirectkey() {
			k = *((*unsafe.Pointer)(k))
		}
		e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
		if checkBucket != noCheck && !h.sameSizeGrow() {
			// 特例：迭代器是在扩展到更大尺寸的过程中启动的
			// 但扩展尚未完成。我们正在处理一个桶，它的
			// 旧桶还没有被疏散。或者至少，当我们启动水桶时，并不是因为
			// 撤离。因此，我们在oldbucket中迭代
			// ，跳过将要转到另一个新bucket的任何键（每个oldbucket在增长期间扩展为两个
			// ）。
			if t.reflexivekey() || t.key.equal(k, k) {
				// 如果旧bucket中的项目不是为
				// 迭代中的当前新bucket指定的，则跳过它。
				hash := t.hasher(k, uintptr(h.hash0))
				if hash&bucketMask(it.B) != checkBucket {
					continue
				}
			} else {
				// 如果k！=k（南）。我们需要一个
				// 可重复和随机选择的方向
				// 在疏散过程中发送NAN。我们将使用tophash的低
				// 位来决定Nan走哪条路。
				// 注意：这种情况就是为什么我们需要两个抽空来散列
				// 值，抽空x和抽空y，它们在
				// 中的低位不同。
				if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
					continue
				}
			}
		}
		if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
			!(t.reflexivekey() || t.key.equal(k, k)) {
			// 这是黄金数据，我们可以退回。
			// 或
			// 键=键，所以条目不能被删除或更新，所以我们可以直接返回它。
			// 这对我们来说很幸运，因为当钥匙打开时=我们无法成功地查找它。
			it.key = k
			if t.indirectelem() {
				e = *((*unsafe.Pointer)(e))
			}
			it.elem = e
		} else {
			// 自迭代器启动以来，哈希表已增长。
			// 这把钥匙的黄金数据现在在其他地方。
			// 检查当前哈希表中的数据。
			// 此代码处理密钥
			// 已被删除、更新或删除并重新插入的情况。
			// 注意：我们需要重新标记密钥，因为它可能已更新为相等（）但不相同的密钥（例如+0.0 vs-0.0）。
			rk, re := mapaccessK(t, h, k)
			if rk == nil {
				continue // 密钥已删除
			}
			it.key = rk
			it.elem = re
		}
		it.bucket = bucket
		if it.bptr != b { // 避免不必要的写入障碍；请参阅问题14921 
			it.bptr = b
		}
		it.i = i + 1
		it.checkBucket = checkBucket
		return
	}
	b = b.overflow(t)
	i = 0
	goto next
}

// mapclear从映射中删除所有键。
func mapclear(t *maptype, h *hmap) {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapclear)
		racewritepc(unsafe.Pointer(h), callerpc, pc)
	}

	if h == nil || h.count == 0 {
		return
	}

	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}

	h.flags ^= hashWriting

	h.flags &^= sameSizeGrow
	h.oldbuckets = nil
	h.nevacuate = 0
	h.noverflow = 0
	h.count = 0

	// 重置哈希种子，使攻击者更难重复触发哈希冲突。见第25237期。
	h.hash0 = fastrand()

	// 保留mapextra分配，但清除任何额外信息。
	if h.extra != nil {
		*h.extra = mapextra{}
	}

	// makebucketaray清除h.bucket指向的内存
	// 并通过生成溢出bucket来恢复所有溢出bucket 
	// 就像新分配了h.bucket一样。
	_, nextOverflow := makeBucketArray(t, h.B, h.buckets)
	if nextOverflow != nil {
		// 如果创建了溢出存储桶，则在初始存储桶创建期间将分配h.extra 
		// 。
		h.extra.nextOverflow = nextOverflow
	}

	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting
}

func hashGrow(t *maptype, h *hmap) {
	// 如果我们达到了负载系数，那么就变大。
	// 否则，溢出桶太多，
	// 因此保持相同的桶数并横向“增长”。
	bigger := uint8(1)
	if !overLoadFactor(h.count+1, h.B) {
		bigger = 0
		h.flags |= sameSizeGrow
	}
	oldbuckets := h.buckets
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
	// 提交grow（原子wrt gc）
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	h.nevacuate = 0
	h.noverflow = 0

	if h.extra != nil && h.extra.overflow != nil {
		// 将当前溢出桶升级到旧一代。
		if h.extra.oldoverflow != nil {
			throw("oldoverflow is not nil")
		}
		h.extra.oldoverflow = h.extra.overflow
		h.extra.overflow = nil
	}
	if nextOverflow != nil {
		if h.extra == nil {
			h.extra = new(mapextra)
		}
		h.extra.nextOverflow = nextOverflow
	}

	// 哈希表数据的实际复制是通过growWork（）和explove（）以增量方式完成的。
}

// overLoadFactor报告放置在1<<B个存储桶中的计数项是否为过载因子。
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// ToomanyOverflowBucket报告noverflow Bucket对于具有1个<B个Bucket的映射是否太多。
// 请注意，这些溢出桶中的大多数必须稀疏使用；
// 如果使用密集，那么我们已经触发了常规地图增长。
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	// 如果阈值太低，我们会做额外的工作。
	// 如果阈值太高，则增长和收缩的映射可能会保留大量未使用的内存。
	// “过多”指（大约）与常规桶一样多的溢出桶。
	// 有关更多详细信息，请参阅incrnoverflow。
	if B > 15 {
		B = 15
	}
	// 编译器在这里没有看到B<16；屏蔽B以生成较短的移位码。
	return noverflow >= uint16(1)<<(B&15)
}

// 增长报告h是否在增长。增长可能是相同的大小或更大。
func (h *hmap) growing() bool {
	return h.oldbuckets != nil
}

// sameSizeGrow报告当前增长是否为相同大小的地图。
func (h *hmap) sameSizeGrow() bool {
	return h.flags&sameSizeGrow != 0
}

// noldbuckets计算当前地图增长之前的桶数。
func (h *hmap) noldbuckets() uintptr {
	oldB := h.B
	if !h.sameSizeGrow() {
		oldB--
	}
	return bucketShift(oldB)
}

// oldbucketmask提供了一个可用于计算n%noldbuckets（）的掩码。
func (h *hmap) oldbucketmask() uintptr {
	return h.noldbuckets() - 1
}

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 确保我们将与
	// 对应的旧桶撤离到我们将要使用的桶中
	evacuate(t, h, bucket&h.oldbucketmask())

	// 再撤离一个旧桶，以取得进展
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

func bucketEvacuated(t *maptype, h *hmap, bucket uintptr) bool {
	b := (*bmap)(add(h.oldbuckets, bucket*uintptr(t.bucketsize)))
	return evacuated(b)
}

// evacDst是一个撤离目的地。
type evacDst struct {
	b *bmap          // 当前目标存储桶
	i int            // 密钥/元素索引到b 
	k unsafe.Pointer // 指向当前密钥存储的指针
	e unsafe.Pointer // 指向当前元素存储的指针
}

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	newbit := h.noldbuckets()
	if !evacuated(b) {
		// TODO:重用溢出存储桶，而不是使用新存储桶，如果存在
		// 则没有使用旧存储桶的迭代器。（If！oldIterator.）

		// xy包含x和y（低和高）疏散目的地。
		var xy [2]evacDst
		x := &xy[0]
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		x.e = add(x.k, bucketCnt*uintptr(t.keysize))

		if !h.sameSizeGrow() {
			// 如果我们越来越大，只计算y指针。
			// 否则GC会看到错误的指针。
			y := &xy[1]
			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			y.k = add(unsafe.Pointer(y.b), dataOffset)
			y.e = add(y.k, bucketCnt*uintptr(t.keysize))
		}

		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			e := add(k, bucketCnt*uintptr(t.keysize))
			for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
				top := b.tophash[i]
				if isEmpty(top) {
					b.tophash[i] = evacuatedEmpty
					continue
				}
				if top < minTopHash {
					throw("bad map state")
				}
				k2 := k
				if t.indirectkey() {
					k2 = *((*unsafe.Pointer)(k2))
				}
				var useY uint8
				if !h.sameSizeGrow() {
					// 计算哈希值以做出疏散决定（我们是否需要
					// 将此密钥/元素发送到存储桶x或存储桶y）。
					hash := t.hasher(k2, uintptr(h.hash0))
					if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
						// 如果键！=键（NaNs），则散列可能（并且可能是
						// 将）与旧散列完全不同。此外，
						// 它是不可复制的。迭代器的存在要求再现性，因为我们的撤离决定必须与迭代器做出的任何决定相匹配。幸运的是，我们有自由发送这些密钥。而且，tophash对于这些类型的键来说是没有意义的。
						// 我们让tophash的低位驱动疏散决策。
						// 我们为下一级重新计算一个新的随机tophash，以便在多次增长后，这些密钥将均匀分布在所有存储桶中。
						useY = top & 1
						top = tophash(hash)
					} else {
						if hash&newbit != 0 {
							useY = 1
						}
					}
				}

				if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
					throw("bad evacuatedN")
				}

				b.tophash[i] = evacuatedX + useY // 疏散X+1==疏散Y 
				dst := &xy[useY]                 // 疏散目的地

				if dst.i == bucketCnt {
					dst.b = h.newoverflow(t, dst.b)
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
				}
				dst.b.tophash[dst.i&(bucketCnt-1)] = top // 屏蔽dst.i作为优化，为避免边界检查
				if t.indirectkey() {
					*(*unsafe.Pointer)(dst.k) = k2 // 复制指针
				} else {
					typedmemmove(t.key, dst.k, k) // 复制元素
				}
				if t.indirectelem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
				} else {
					typedmemmove(t.elem, dst.e, e)
				}
				dst.i++
				// 这些更新可能会将这些指针推过
				// 键或元素数组的末尾。没关系，因为我们在bucket的末尾有一个溢出指针
				// 来防止指针指向bucket的末尾。
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.e = add(dst.e, uintptr(t.elemsize))
			}
		}
		// 取消溢出存储桶的链接并清除key/elem以帮助GC。
		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
			// 保留b.tophash，因为疏散
			// 状态保持在那里。
			ptr := add(b, dataOffset)
			n := uintptr(t.bucketsize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}

	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}

func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
	h.nevacuate++
	// 实验表明1024的杀伤力至少超过一个数量级。
	// 无论如何，把它放在那里作为保护措施，以确保O（1）行为。
	stop := h.nevacuate + 1024
	if stop > newbit {
		stop = newbit
	}
	for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
		h.nevacuate++
	}
	if h.nevacuate == newbit { // newbit==#旧桶的
		// 增长已经完成。释放旧的主桶阵列。
		h.oldbuckets = nil
		// 也可以丢弃旧的溢出桶。
		// 如果迭代器仍然引用它们，则迭代器将保留指向该切片的指针。
		if h.extra != nil {
			h.extra.oldoverflow = nil
		}
		h.flags &^= sameSizeGrow
	}
}

// 反映存根。调用自../reflect/asm.*.s 

// go:linkname reflect\u makemap reflect.makemap 
func reflect_makemap(t *maptype, cap int) *hmap {
	// 检查不变量并反映数学。
	if t.key.equal == nil {
		throw("runtime.reflect_makemap: unsupported map key type")
	}
	if t.key.size > maxKeySize && (!t.indirectkey() || t.keysize != uint8(sys.PtrSize)) ||
		t.key.size <= maxKeySize && (t.indirectkey() || t.keysize != uint8(t.key.size)) {
		throw("key size wrong")
	}
	if t.elem.size > maxElemSize && (!t.indirectelem() || t.elemsize != uint8(sys.PtrSize)) ||
		t.elem.size <= maxElemSize && (t.indirectelem() || t.elemsize != uint8(t.elem.size)) {
		throw("elem size wrong")
	}
	if t.key.align > bucketCnt {
		throw("key align too big")
	}
	if t.elem.align > bucketCnt {
		throw("elem align too big")
	}
	if t.key.size%uintptr(t.key.align) != 0 {
		throw("key size not a multiple of key align")
	}
	if t.elem.size%uintptr(t.elem.align) != 0 {
		throw("elem size not a multiple of elem align")
	}
	if bucketCnt < 8 {
		throw("bucketsize too small for proper alignment")
	}
	if dataOffset%uintptr(t.key.align) != 0 {
		throw("need padding in bucket (key)")
	}
	if dataOffset%uintptr(t.elem.align) != 0 {
		throw("need padding in bucket (elem)")
	}

	return makemap(t, cap, nil)
}

// go:linkname reflect\u mapaccess reflect.mapaccess 
func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	elem, ok := mapaccess2(t, h, key)
	if !ok {
		// reflect对缺少的元素要求为零
		elem = nil
	}
	return elem
}

// go:linkname reflect\u mapassign reflect.mapassign 
func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, elem unsafe.Pointer) {
	p := mapassign(t, h, key)
	typedmemmove(t.elem, p, elem)
}

// go:linkname reflect\u mapdelete reflect.mapdelete 
func reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	mapdelete(t, h, key)
}

// go:linkname reflect\u mapiterinit reflect.mapiterinit 
func reflect_mapiterinit(t *maptype, h *hmap) *hiter {
	it := new(hiter)
	mapiterinit(t, h, it)
	return it
}

// go:linkname reflect\u MapiterText reflect.MapiterExt 
func reflect_mapiternext(it *hiter) {
	mapiternext(it)
}

// go:linkname reflect\u mapiterkey reflect.mapiterkey 
func reflect_mapiterkey(it *hiter) unsafe.Pointer {
	return it.key
}

// go:linkname reflect\u mapiterelem reflect.mapiterelem 
func reflect_mapiterelem(it *hiter) unsafe.Pointer {
	return it.elem
}

func reflect_maplen(h *hmap) int {
	if h == nil {
		return 0
	}
	if raceenabled {
		callerpc := getcallerpc()
		racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen))
	}
	return h.count
}

func reflectlite_maplen(h *hmap) int {
	if h == nil {
		return 0
	}
	if raceenabled {
		callerpc := getcallerpc()
		racereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen))
	}
	return h.count
}

const maxZero = 1024 // 必须与reflect/value中的值匹配。go:maxZero cmd/compile/internal/gc/walk.go:zerovalize 
var zeroVal [maxZero]byte
